#include "trie.h"
#define IP_NUM 000000
#define MEM_GROW_SIZE 1000 /*<!初始化内存用完后，继续申请的内存个数*/
#define INIT_MEM_SIZE 10000000 /*<!初始化时内存分配个数*/

/*<! trie树结点结构*/
typedef struct trie_node {
    bool isNet;				  /*<! 记录此处是否构成一个串*/
	UINT black;
	UINT white;
    struct trie_node *next[2];/*<!指向各个子树的指针*/
}trie_node;

/*
 * @note trie树根结点
 */
trie_node *root;


/*!
 *@param x [I] IP地址对应的长整数
 *@param data [O] 得到的32位二进制数
 *@param len [I] 参数data的空间长度,大于等于33
 *@note 网络字节序的长整数转化为32位二进制数
 */
static int trans(unsigned  int x,char *data,int len) 
{ 
    if (NULL == data)
		return 1;

	x = ntohl(x);
	if( len <33)
		return 2;

    int a[32];
    int i =0;
    UINT rem; 
    do{ 
        rem=x%2;x=x/2; 
        a[i]=rem; 
        i++; 
    }while(x!=0);
    for(;i<32;i++)
        a[i] = 0; 
    while(--i>=0) 
        *(data+31-i)=a[i]+'0'; 
    *(data+32) = '\0';
	
	return 0;
} 

/*!
 *@param ipaddr [I] 32位二进制串
 *@param subnet [O] 得到的点分十进制的子网IP
 *@param sublen [I] subnet缓冲区的长度
 *@return 成功返回0 ，否则返回1
 */
static int get_subnet_ip(char *ipaddr,char *subnet,int sublen)
{
	if( NULL == ipaddr || NULL == subnet)
		return 2;

	ipaddr[sublen] = '\0';
	char temp[33];
	strcpy(temp,ipaddr);
	strncat(temp,"00000000000000000000000000000000",32-sublen);
	UINT lip = strtoul(temp,NULL,2);
	lip = htonl(lip);
	char strip[16];
	const char *ret = inet_ntop(AF_INET,&lip,strip,16);
	if(NULL == ret) {
		return 1;
	}
	else {
		strcpy(subnet,strip);
		return 0;
	}
}

/*!
 *@param input_str [I] 输入的子网字符串
 *@param bi_subnet [O] 提取出的子网二进制串
 *@param len [I] bi_subnet区域的大小,大于等于33
 *@return 成功返回子网串的长度,失败返回负值
 */
static int 
trim_binary_subnet(const char *input_str ,char* bi_subnet,int len)
{
	if(NULL == input_str || NULL == bi_subnet )
		return -1;

	if (len <33) 
		return -5;

#ifdef SCREEN
	printf("input str is %s\n",input_str);
#endif
	char *p;
	p = strchr(input_str,'/');
	if(NULL == p)
		return -2;

	int sublen = atoi(p+1);
	if(0 == sublen ||sublen >32)
		return -3;

	memset(bi_subnet,'\0',33);
	memcpy(bi_subnet,input_str,p-input_str);
	struct in_addr myin;
	int ret ;
    ret = inet_pton(AF_INET,bi_subnet,&myin);/*<!成功返回1 ，失败返回0*/
	if(ret != 1)
		return -4;

    trans(myin.s_addr,bi_subnet,33);
	bi_subnet[sublen] = '\0';

	return sublen;
}
/*!
*@param subnet 要删除的子网串
*@note  从trie树中删除一个子网
*@return 成功返回0，否则返回非0
*/
int remove(const char* subnet)
{   
	if(NULL == subnet)
		return 1;

    trie_node *location = root;   
    trie_node *parent ;
    while( location!=NULL && *subnet!=0) {  
    	parent = location;
        location = location->next[*subnet-'0'];   
        subnet++;
    	if('\0' == *subnet) {
            if(NULL == location) {
                return 2 ;
            }
            else if(location &&NULL == location->next[0]&&NULL == location->next[1]) {        
#ifdef SCREEN
                printf("remove node :%p\n",location);
#endif
                free_node(location);
                parent->next[*(subnet-1)-'0'] =NULL;
                return  0;
            }
            else {
				if(true == location->isNet) { 
                	location->isNet = false;
                	return  0;
				}
				else {
					return 3;
				}
            }
        }
    }    
	if(NULL == location )//trie中没匹配到
		return 3;

	return 0;
}
/*!
*@param subnet 要删除的子网串 格式为 2.2.2.2/18
*@note  从trie树中删除一个子网
*@return 成功返回0，否则返回非0
*/
int remove_subnet(const char* subnet)
{
	if(NULL == subnet)
		return 1;

	char ipaddr[33];
	int sublen =trim_binary_subnet(subnet,ipaddr,33);
	if(sublen <0)
		return 2;

#ifdef SCREEN
	char subnetIP[16];
	if(0 != get_subnet_ip(ipaddr, subnetIP,sublen)) 
		return 4;

	printf("subnet ip is %s \n",subnetIP);
#endif
	if(0 != remove(ipaddr))
		return 3;

	return 0;
}

/*!
*@return 成功返回0 ，否则返回1
*@note 回收trie树的内存
*/
int delete_trie()
{
    if(0== delete_memorypool())
        return 0;
    else 
        return 1;
}

/*!
*@param subnet 要插入到树的二进制字符串
*@param balck  黑名单对应的wildcard 如果为0 说明未启用
*@param white  白名单对应的wildcard 如果为0 说明未启用
*@note 向trie树插入一个subnet
*@return 成功返回0，否则返回1
*/
int insert(char* subnet,UINT black ,UINT white)
{
    trie_node *location = root;

    while(*subnet) {
        if(location->next[*subnet-'0'] == NULL) {/* 不存在则建立*/
            trie_node *tmp = (trie_node*)alloc_node();
	        if(NULL == tmp)
	            return 1;

	       	tmp->isNet = false;
			tmp->black = 0;
			tmp->white = 0;
		    tmp->next[0] = NULL;
	        tmp->next[1] = NULL;
            location->next[*subnet-'0'] = tmp;
#ifdef SCREEN
            //printf("Create node %p,%d\n",tmp,count++);
#endif
        }    
        location = location->next[*subnet-'0']; /* 每插入一步，相当于有一个新串经过，指针要向下移动*/
        subnet++;
    }
    location->isNet = true; /*到达尾部,标记一个串*/
	location->black = black;
	location->white = white;

    return 0;
}

/*!
*@param subnet 要插入到树的二进制字符串 格式为2.2.2.2/18
*@param balck  黑名单对应的wildcard 如果为0 说明未启用
*@param white  白名单对应的wildcard 如果为0 说明未启用
*@note 向trie树插入一个subnet
*@return 成功返回0，否则返回1
*/
int insert_subnet(const char *subnet,UINT black ,UINT white)
{
	if(NULL == subnet)
		return 1;

	char ipaddr[33];
	int sublen =trim_binary_subnet(subnet,ipaddr,33);
	if(sublen <0)
		return 2;

#ifdef SCREEN
	char subnetIP[16];
	if(0 != get_subnet_ip(ipaddr ,subnetIP,sublen)) 
		return 4;

	printf("subnet ip is %s \n",subnetIP);
#endif
	if(0 != insert(ipaddr,black,white))
		return 3;

    return 0;
}

/*!
*@param subnet [I] 要查找的IP
*@param pos [O] 返回子网在原IP的位置
*@param balck  黑名单对应的wildcard 如果为0 说明未启用
*@param white  白名单对应的wildcard 如果为0 说明未启用
*@note 从trie树中查找给定IP的子网
*@return 找到返回0 否则返回非0
*/
static int
search(char *subnet,int *pos,UINT *black ,UINT *white)
{
	if(NULL == subnet)
		return 1;

    trie_node *location = root;
	trie_node *parent = location;
	int  latest = -1;
	trie_node *plate;
    char *p = subnet;
    int tpos =0;
	
    while(*p&& location) {
		parent = location;
		if(true == location->isNet) {/*<! 最近一次匹配到子网的位置*/
			latest = tpos ;
			plate = location;
		}
        location = location->next[*p-'0'];
        p++;
        tpos++;
    }

    if(NULL == location) {
        --tpos;
    }
	else if(true == location->isNet) {
		*pos = tpos;
		*black = location->black;
		*white = location->white;
		return 0;
	}
	
	if( true == parent->isNet) {
		*pos = tpos;
		*black = parent->black;
		*white = parent->white;
		return 0;
	}
	else {
		if(-1 == latest) {
			*pos = 0;
			return 2;
		}
		else {
			*pos = latest;
			*black = plate->black;
			*white = plate->white;
			return 0;
		}
	}
}

/*!
 * 本函数接收一个网络字节序的ip数值，在trie中查找对应的子网
 * 如果子网存在，则已字符ip/数值（2.2.2.2/20）的格式存入到
 * 用户指定的缓存subnet中，要注意缓冲的长度要大于等于20，因为
 * 200.200.200.200/20是最长的返回形式，需要20个字符空间。另外
 * 使用时，一定要先判断返回值，如果返回0 ，则说明找到子网，subnet
 * 中有值，如果返回值不为0 ，则没找到，subnet中什么都没有
 *@param uip [I] 要查找的IP整数值
 *@param subnet [o] 得到的子网号缓冲,缓冲长度要大于等于20
 *@param balck  黑名单对应的wildcard 如果为0 说明未启用
 *@param white  白名单对应的wildcard 如果为0 说明未启用
 * 返回结果为2.2.2.2/20格式
 *@return 成功得到子网号返回1 否则返回0
 */
int get_subnet(UINT uip ,char *subnet,UINT *black ,UINT *white)
{
	if( NULL == subnet)
		return 0;
		
	char data[33];
	trans(uip,data,33);
	int pos;
	if(0 != search(data,&pos,black,white))
		return 0;

	char tempip[20];
	if(0 !=	get_subnet_ip(data,tempip,pos))
		return 0;

#ifdef SCREEN
	printf("%s %s\n",tempip,data);
#endif
	strcat(tempip,"/");
	char slen[3];
	sprintf(slen,"%d",pos);
	strcat(tempip,slen);
	strcpy(subnet,tempip);

	return 1;
}
/*!
 *@param input_str [I] 要查找的IP，2.2.2.2格式
 *@param subnet [o] 得到的子网号缓冲,缓冲长度要大于等于20
 *@param balck  黑名单对应的wildcard 如果为0 说明未启用
 *@param white  白名单对应的wildcard 如果为0 说明未启用
 * 返回结果为2.2.2.2/20格式
 */
static int
retrieve_net(char *input_str ,char *subnet,UINT *black ,UINT *white)
{
	if(NULL == input_str || NULL == subnet )
		return -1;

	struct in_addr myin;
	int ret ;
    ret = inet_pton(AF_INET,input_str,&myin);/*<!成功返回1 ，失败返回0*/
	if(ret != 1)
		return -2;

	if(get_subnet(myin.s_addr,subnet,black,white) !=0)
		return -3;

	return 0;
}
/*!
*@param input_str 要修改的网络的字符串 格式为2.2.2.2/18
*@param balck  黑名单对应的wildcard 如果为0 说明未启用
*@param white  白名单对应的wildcard 如果为0 说明未启用
*@note 修改trie树一个subnet
*@return 成功返回0，否则返回非0
*/
int modify_subnet(const char* input_str ,UINT black,UINT white)
{
	if(NULL == input_str )
		return -1;
		
	char *p;
	p = strchr(input_str,'/');
	if(NULL == p)
		return -2;

	char bi_subnet[16];
	memset(bi_subnet,'\0',16);
	memcpy(bi_subnet,input_str,p-input_str);
	struct in_addr myin;
	int ret ;
    ret = inet_pton(AF_INET,bi_subnet,&myin);/*<!成功返回1 ，失败返回0*/
	char tmp[20];
	UINT b,w;
	if(retrieve_net(bi_subnet,tmp,&b,&w) != 0) /*<! 先查找有没有此网络号*/
		return -3;

	if(0 == strcmp(tmp,input_str))
	{
		if(black == b && white ==w) /*<! 已经存在，并且黑白名单相同，则不修改*/ 	
			return 0;
		if( 0 != insert_subnet(input_str,black,white))
			return -4;
	}

	return -5;
}
/*!
 *@param init_mem_num 初始时向系统申请的存放trie结点内存的个数
 *@note 程序结束之前，要调用delete_trie()回收内存 
 *@return 成功返回0 否则返回1
 */
int init_trie(UINT init_mem_num) //简单测试
{
	if(NULL != root) /*<!已经初始化过了*/
		return 0;

    int ret = init_memorypool(sizeof(trie_node),init_mem_num,MEM_GROW_SIZE);
	if (ret != 0)
		return 1;

    root  = (trie_node*)alloc_node();
	if(NULL == root)
		return 2;

	root->isNet = false;
	root->black = 0;
	root->white = 0;
    root->next[0] = NULL;
    root->next[1] = NULL;

    return 0;
}
